package com.zxy.leetcode._00100_00199._00120_00129;

/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 *
 * 买卖股票的最佳时机
 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。
 * 设计一个算法来计算你所能获取的最大利润。
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 */
public class Test00121 {

    public static void main(String[] args) {
        Test00121 test = new Test00121();

        int[] nums1 = {7,1,5,3,6,4};
        System.out.println(test.maxProfit(nums1) == 5);

        int[] nums2 = {7,6,4,3,1};
        System.out.println(test.maxProfit(nums2) == 0);
    }

    /*
    根据分析，找出最大差序列就可以了
     */
    public int maxProfit(int[] prices) {
        if (prices.length <= 1){
            return 0;
        }

        int maxSum = 0;
        int min = prices[0];
        int sum;
        for (int i=1; i<prices.length; i++) {
            sum = prices[i] - min;  // 现在卖，能转最多多少钱
            if (sum > maxSum) {
                maxSum = sum;
            }
            if (prices[i] < min) {  // 当前是低点，可能是一个买入点
                min = prices[i];
            }
        }

        return maxSum;
    }

}
